README.md

1139. Largest 1-Bordered Square

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]] Output: 9 

Example 2:

Input: grid = [[1,1,0,0]] Output: 1 

Constraints:

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is 0 or 1

Solutions (Rust)

1. Solution

implSolution{pubfnlargest1_bordered_square(grid:Vec<Vec<i32>>) -> i32{let row_len = grid.len();let col_len = grid[0].len();letmut prefix_sum_row = vec![vec![0; col_len]; row_len];letmut prefix_sum_col = vec![vec![0; col_len]; row_len];letmut max_len = 0;for row in0..row_len {for col in0..col_len {if grid[row][col] == 0{continue;}if col > 0{ prefix_sum_row[row][col] = prefix_sum_row[row][col - 1];}if row > 0{ prefix_sum_col[row][col] = prefix_sum_col[row - 1][col];} prefix_sum_row[row][col] += 1; prefix_sum_col[row][col] += 1;for len in(max_len + 1..=prefix_sum_row[row][col].min(prefix_sum_col[row][col])).rev(){if prefix_sum_row[row + 1 - len][col] >= len && prefix_sum_col[row][col + 1 - len] >= len { max_len = len;break;}}}}(max_len * max_len)asi32}}